package com.lzhsite.leetcode.algoritom.practise.dynamicProgramming;

//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

//上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）

public class LeetCode042接雨水 {
	/**
	 * 解题思路：利用两个辅助数组left[]和right[] left[i]、
	 * right[i]分别表示i位置左边所有数的最大值和i位置右边所有数的最大值
	 * 若height[i] < left[i] && height[i] < right[i]，则i位置积水，且积水量为min(left[i],
	 * right[i]) - height[i]
	 **/
	private static int trap(int arr[]) {

		int left[] = new int[arr.length];
		int right[] = new int[arr.length];
		int max = 0;
		left[0] = 0;
		right[arr.length - 1] = 0;
		for (int i = 1; i < arr.length; i++) {
			max = Math.max(max, arr[i - 1]);
			left[i] = max;
		}
		max = 0;
		for (int i = arr.length - 2; i > -1; i--) {
			max = Math.max(max, arr[i + 1]);
			right[i] = max;
		}

		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			if (Math.min(left[i], right[i]) > arr[i]) {
				sum = sum + Math.min(left[i], right[i]) - arr[i];
			}

		}
		return sum;
	}

	/**
	 * 每次都要算某个柱子的左右最值，时间复杂度是O(n2)，能不能把算左右最值的效率提高呢？ 这就用到动态规划了，假如说
	 * 我们用函数f(n)，表示到第n个柱子（包括第n个柱子）左边的最大值，
	 * 则f(n)=max(f(n-1)，height[n])，其中height[n]为第n个柱子的高度，右边同理
	 */

	public int trap2(int[] height) {
		int sum = 0;
		int len = height.length;
		if (len == 0)
			return 0;
		int[] maxLeft = new int[len];
		int[] maxRight = new int[len];
		maxLeft[0] = height[0];
		for (int i = 1; i < len; i++) {
			maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
		}
		maxRight[len - 1] = height[len - 1];
		for (int i = len - 2; i >= 0; i--) {
			maxRight[i] = Math.max(height[i], maxRight[i + 1]);
		}
		for (int i = 0; i < height.length; i++) {
			sum += Math.min(maxLeft[i], maxRight[i]) - height[i];
		}
		return sum;
	}

	public static void main(String[] args) {
		int[] arr = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
		System.out.println(trap(arr));
	}

}
